/* Emamul Islam Emon.      Id No: 093-15-844

9)	Example of Marge Sort.*/


#include<stdio.h>
#include<conio.h>
#include<values.h>

#define MAX 10

void Merge(int p, int q, int r);
void MergeSort (int p, int r);

int A[MAX];

void main(){
	int c,i;
	clrscr();
	printf("Plz enter how many data u would like to sort(Not more than 10):");
	scanf("%d",&c);
	printf("Plz enter the data u would like to sort:");
	for(int i=0;i<c;i++){
		scanf("%d",&A[i]);
	}
	printf("Unsorted Data:");
	for(i=0;i<c;i++){
		printf("%d ",A[i]);
	}
	MergeSort(0,c-1);
	printf("Sorted Data:");
	for(i=0;i<c;i++){
		printf("%d ",A[i]);
	}
	getch();
}



void MergeSort (int p, int r){   // sort A[p..r] by divide & conquer
	int q;
	if(p < r){
		q=(p+r)/2;
		MergeSort(p, q);
		MergeSort(q+1, r);
		Merge (p, q, r); // merges A[p..q] with A[q+1..r]
	}
}


void Merge(int p, int q, int r){
	int L[MAX];
	int R[MAX];
	int n1= q - p + 1;
	int n2= r - q;
	int i,j;
	for(i= 1;i<=n1;i++)
		L[i]= A[p + i-1];
	for(j=1;j<=n2;j++)
		R[j]=A[q+j];
	L[n1+1]=MAXINT;
	R[n2+1]=MAXINT;
	i=1;
	j=1;
	for (int k=p;k<=r;k++){
		if(L[i]<= R[j]){
			A[k]= L[i];
			i = i + 1;
		}
		else{
			A[k] = R[j];
			j = j + 1;
		}
	}
}



















































